#include <iostream>
#include <vector>
#include <set>
using namespace std;

// 81.04 %
class Solution
{
  public:
	bool containsNearbyAlmostDuplicate(vector<int> &nums, int k, int t)
	{
		set<long long> record;
		for (int i = 0; i < nums.size(); i++)
		{
			if (record.lower_bound((long long)nums[i] - t) != record.end() && *record.lower_bound((long long)nums[i] - t) <= (long long)nums[i] + t)
				return true;
			record.insert(nums[i]);
			if (record.size() == k + 1)
			{
				record.erase(nums[i - k]);
			}
		}
		return false;
	}
};

int main()
{
	int nums[] = {1, 2, 3, 1}, k = 2, t = 3;
	int len = sizeof(nums) / sizeof(nums[0]);
	vector<int> myVector(nums, nums + len);
	cout << Solution().containsNearbyAlmostDuplicate(myVector, k, t) << endl;
	return 0;
}
